// 1.讲一下排序，给一个不懂快排的人讲快排，复杂度，为什么他叫快排

// 时间复杂度: O(N*logN) 快排效率最高

// 思路：快速排序会将原始数组筛选成较小和较大的两个子数组，然后递归的排序两个子数组
let arr = [3, 4, 6, 9, 0, 2, 1]
function quickSort(arr) {
  if (arr.length > 1) {
    let lineIndex = Math.floor(arr.length / 2)
    let pivot = arr.splice(lineIndex, 1)[0]
    let left = []
    let right = []

    for (let i = 0; i < arr.length; i++) {
      if (arr[i] < pivot) left.push(arr[i])
      else right.push(arr[i])
    }

    return quickSort(left).concat([pivot], quickSort(right))
  } else return arr
}


function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}

function partition(arr, left, right) {
  // 划分左右子数组
  let privotValue = Math.floor(left + (right - left) / 2)
  let i = left
  let j = right
  while (i <= j) {
    while (arr[i] < privotValue) {
      i++
    }
    while (arr[j] > privotValue) {
      j--
    }
    if (i <= j) {
      swap(arr, i, j)
      i++
      j--
    }
  }
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (arr.length > 1) {
    const lineIndex = partition(arr, left, right)

    // 左边子数组长度不小于1
    if (left < lineIndex - 1) {
      quickSort(arr, left, lineIndex - 1)
    }

    // 右边边子数组长度不小于1
    if (lineIndex < right) {
      quickSort(arr, left, lineIndex - 1)
    }

  }
  return arr
}


console.log(quickSort(arr));